class Solution1 {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[i]) {
                    g[i] = Math.max(f[j] + 1, g[j]);
                } else if (nums[j] < nums[i]) {
                    f[i] = Math.max(g[j] + 1, f[j]);
                }
            }

        }

        int ret = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret, f[i]);
            ret = Math.max(ret, g[i]);
        }

        return ret;
    }
}

class Solution2 {
    public int addDigits(int num) {
        while(num > 10) {
            num = add(num);
        }
        return num;
    }

    public int add(int n) {
        int sum = 0;
        while (n != 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
}

//public class Solution3 extends GuessGame {
//    public int guessNumber(int n) {
//        int left = 1, right = n;
//        while(left < right) {
//            int mid = left + (right - left) / 2;
//            System.out.println(mid);
//            if(guess(mid) == 0) {
//                return mid;
//            }else if(guess(mid) == -1) {
//                right = mid;
//            }else if(guess(mid) == 1) {
//                left = mid+1;
//            }
//        }
//        return left;
//    }
//}

class Solution5 {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else if(nums[mid] > target) {
                right = mid;
            }
        }
        if(nums[left] < target) return left + 1;
        return left;
    }
}
//
//public class Solution extends VersionControl {
//    public int firstBadVersion(int n) {
//        long left = 1, right = n;
//        while(left < right) {
//            long mid = left + (left - right) / 2;
//            if(isBadVersion(mid) == false) {
//                right = mid;
//            }else {
//                left = mid+1;
//            }
//        }
//        return (int)left;
//    }
//}

public class Main {
}
